1005. K 次取反后最大化的数组和

Similar Question

Solution Tips

方案一: 贪心

var largestSumAfterKNegations = function(nums, k) {
    // 需要知道负数和k的关系
    // 如果负数个数 >= k , 找到最小的 k 个负数, 全部反转为正数
    // 如果负数个数 < k, 所有的负数都先进行一次反转, 剩余的次数就去操作最接近0的那个数
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    let ans = _.sum(nums);
    for (let i = -100; i < 0; ++i) {
        if (freq.has(i)) {
            const ops = Math.min(k, freq.get(i));
            ans += (-i) * ops * 2;
            freq.set(i, freq.get(i) - ops);
            freq.set(-i, (freq.get(-i) || 0) + ops);
            k -= ops;
            if (k === 0) {
                break;
            }
        }
    }
    if (k > 0 && k % 2 === 1 && !freq.has(0)) {
        for (let i = 1; i <= 100; ++i) {
            if (freq.has(i)) {
                ans -= i * 2;
                break;
            }
        }
    }
    return ans;
};